package com.dataStructures.linkedlist;

import lombok.Getter;
import lombok.Setter;

/**
 * 约瑟夫问题 - 创建环形链表
 */
public class Josepfu {
	public static void main(String[] args) {
		CircleSingleLinkedList list = new CircleSingleLinkedList(5);
		list.show();
		list.countBoy(1, 2, 5);
	}
}

/**
 * 环形单向列表
 */
class CircleSingleLinkedList {

	public CircleSingleLinkedList(int num) {
		this.addBoy(num);
	}

	public CircleSingleLinkedList() {
	}

	/**
	 * first 节点
	 */
	private Boy first = null;

	/**
	 * 添加小孩，构建环形链表
	 */
	public void addBoy(int nums) {
		if (nums < 1) {
			System.out.println("error input");
			return;
		}
		Boy cur = null;
		for (int i = 1; i <= nums; i++) {
			Boy boy = new Boy(i);
			if (1 == i) {
				first = boy;
				first.setNext(first);
				cur = first;
			} else {
				cur.setNext(boy);
				boy.setNext(first);
				cur = boy;
			}
		}
	}

	/**
	 * 遍历输出循环列表
	 */
	public void show() {
		if (first == null) {
			System.out.println("empty list");
			return;
		}
		Boy temp = first;
		while (true) {
			System.out.printf("boy num is %d\n", temp.getNo());
			if (temp.getNext() == first) {
				break;
			}
			temp = temp.getNext();
		}
	}

	/**
	 * 根据用户输入，计算出小孩出圈位置
	 *
	 * @param startNo  开始数的位置
	 * @param countNum 数几下
	 * @param nums     小孩数量
	 */
	public void countBoy(int startNo, int countNum, int nums) {
		if (startNo < 1 || startNo > nums || countNum < 1 || countNum > nums || first == null) {
			System.out.println("error input");
			return;
		}
		// 创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
		Boy helper = first;
		while (helper.getNext() != first) {
			helper = helper.getNext();
		}
		// 找到开始报数的位置（first 和 helper 移动 startNo - 1 次）
		for (int i = 0; i < startNo - 1; i++) {
			first = first.getNext();
			helper = helper.getNext();
		}
		// 报数出圈（first 和 helper 移动 countNum - 1 次）
		while (helper != first) {
			for (int i = 0; i < countNum - 1; i++) {
				first = first.getNext();
				helper = helper.getNext();
			}
			// 这时 first 指向的节点，就是要出圈的小孩节点
			System.out.printf("boy no: %d out\n", first.getNo());
			first = first.getNext();
			helper.setNext(first);
		}
		System.out.printf("the last boy's no is %d\n", first.getNo());
	}
}

@Getter
@Setter
class Boy {
	private int no;
	private Boy next;

	public Boy(final int no) {
		this.no = no;
	}
}